#include <malloc.h>
#include <iostream>
using namespace std;

typedef int datatype;
typedef struct node     /*结点类型定义*/
{
    datatype data;         /*数据域*/
    struct node *next;     /*next为指针域，指向该结点的后继*/
}SList;
SList *head1,*head2,*head3,*p;       /*指针类型说明*/

int score[10]={77,88,99,60,87,100,50,85,90,56};

SList *CreateListF();/*头插法*/
SList *CreateListR();/*尾插法*/
SList *CreateListRP();/*改进尾插法*/

void InsertBefore(SList *head,SList *p,datatype x);
void InsertAfter(SList *p,datatype x);
SList *Get(SList* head, int id);
int LOCATE(SList* head, datatype key);
void DeleteA(SList *p);
void ShowSList(SList* head);

int main()
{
    SList *p1;

    head1=CreateListF();
    cout<<"头插建表结果head1："<<endl;
    ShowSList(head1);

    head2=CreateListR();
    cout<<"尾插建表结果head2："<<endl;
    ShowSList(head2);

    head3=CreateListRP();
    cout<<"改进尾插建表结果head3："<<endl;
    ShowSList(head3);

    p1=Get(head1, 2);
    cout<<"The 2nd node of the 1st list is "<<p1->data<<endl;

    p1=Get(head3, 2);
    cout<<"The 2nd node of the 3rd list is "<<p1->data<<endl;

    int id=LOCATE(head2, 6);
    if (id==-1) cout<<"LOCATE 6 FAILURE!"<<endl;
    else cout<<"LOCATE 6 SUCCESS"<<endl;

    id=LOCATE(head3, 100);
    if (id==-1) cout<<"LOCATE 100 FAILURE!"<<endl;
    else cout<<"LOCATE 100 SUCCESS,it's at No. "<<id<<" position!"<<endl;

    p1=Get(head3, 3);
    DeleteA(p1);
    cout<<"Delete the 4th node:\n";
    ShowSList(head3);

    p1=Get(head3, 5);
    InsertAfter(p1,999);
    InsertBefore(head3,p1,888) ;
    cout<<"Insert before and after the 5th node\n";
    ShowSList(head3);
}


SList *CreateListF()      /*头插法*/
{
    int i;     /*逐个插入字符，以"$"为结束符，返回单链表头指针*/
    SList *head,*s;
    head=NULL;    /*链表开始为空*/
    for (i=0;i<10;i++)
    {
        s=(SList *)malloc(sizeof(SList));   /*生成新结点*/
        s->data=score[i];
        s->next=head;
        head=s;
    }
    return head;
}

SList *CreateListR()   /*尾插法*/
{
    int i;
    SList *head,*s,*r;
    head=NULL;           /*链表开始为空*/
    r=NULL;              /*尾指针初值为空*/
    for (i=0;i<10;i++)
    {
        s=(SList *)malloc(sizeof(SList));  /*生成新结点*/
        s->data=score[i];
        if (head==NULL) head=s;
        else r->next=s;
        r=s;
    }
    if (r!=NULL) r->next=NULL;
    return head;
}

SList *CreateListRP()     /*改进尾插法*/
{
    int i;
    SList *head,*s,*r;
    head=(SList *)malloc(sizeof(SList));  /*生成头结点*/
    head->data=0;
    r=head;          /*尾指针初值指向头结点*/
    for (i=0;i<10;i++)
    {
        s=(SList *)malloc(sizeof(SList));  /*生成新结点*/
        s->data=score[i];
        r->next=s;     /*新结点插入表尾*/
        r=s;           /*尾指针r指向新的表尾*/
    }
    r->next=NULL;
    return head;
}

SList *Get(SList* head, int id)
{
    int i=1;          /*巡访计数指针,从第一元素开始*/
    SList*  p;
    p=head;            /*从头结点起巡访扫描*/
    if (p->data==0)  {p=p->next;} /*对有头结点的链表进行特殊处理*/

    while((p->next!=NULL)&&(i<id))
    {
        p=p->next;
        i++;
    }
    if (i==id) return p;
    else return NULL;
}

int LOCATE(SList* head, datatype key)
{
    int i=1;             /*巡访计数指针,从第一元素开始*/
    SList*  p;
    p=head;              /*从头结点起巡访扫描*/
    if (p->data==0)  {p=p->next;} /*对有头结点的链表进行特殊处理*/

    while(p!=NULL)   /*扫描整个表*/
        if (p->data!=key) {p=p->next;i++;}
        else break;
    if (p==NULL) return -1;
    else return i;
}

void InsertAfter(SList *p,datatype x)  /*将值为X的新结点插入*P之后*/
{
    SList *s;
    s=(SList *)malloc(sizeof(SList));  /*生成新结点*/
    s->data=x;
    s->next=p->next;p->next=s;      /*将*s插入*p之后*/
}

void InsertBefore(SList *head,SList *p,datatype x)
/*在带头结点的单链表head中,将值为X的新结点插入*P之前*/
{
    SList *q,*s;
    s=(SList *)malloc(sizeof(SList));  /*生成新结点*/
    s->data=x;
    q=head;                     /*从头指针开始*/
    while(q->next!=p) q=q->next; /*找*p的前趋结点*/
    s->next=p;
    q->next=s;                  /*将*s插入*p之 前*/
}

void DeleteA(SList *p)  /*删除*p的后继结点*n,设*n存在*/
{
    SList *n;
    if(p->next!=NULL)
    {
        n=p->next;
        p->next=n->next;
        free(n);
    }
}

void ShowSList(SList* head)
{
    SList *p;
    p=head;

    if (p->data==0) p=p->next;  /*对有头结点的链表进行特殊处理*/

    while(p->next!=0)
    {
        cout<<p->data<<"-->";
        p=p->next;
    }
    cout<<p->data<<"\n";
}





